package test.n00400;


import java.util.ArrayList;
import java.util.List;

import static utils.Tools.listOf;

public class Problem00470 {
    public static void main(String[] args) {
        println(new int[]{1, 2, 3});
        println(new int[]{1});
        println(new int[]{1, 1, 2});
        println(new int[]{1, 1, 1, 2, 2});
    }

    public static void println(int[] nums) {
        Solution ss = new Solution();
        System.out.println(listOf(nums) + "," + ss.permuteUnique(nums));
    }

    public static class Solution {

        /**
         * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
         * <p>
         * 解题思路:
         * 回溯+深度优先搜索(dfs)
         *
         * @param nums
         * @return
         */
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> result = new ArrayList<>();

            int len = nums.length;
            if (len == 0) {
                return result;
            }

            final List<Integer> path = new ArrayList<>();
            final boolean[] used = new boolean[nums.length];
            dfs(nums, len, 0, path, used, result);
            return result;
        }

        private void dfs(
                int[] nums,
                int len,
                int depth,
                List<Integer> path,
                boolean[] used,
                List<List<Integer>> result
        ) {
            if (len == depth) {
                result.add(new ArrayList<>(path));
                return;
            }

            for (int i = 0; i < len; i++) {
                if (used[i]) {
                    continue;
                }

                if (i > 0 && nums[i] == nums[i - 1] && !used[i-1]) {
                    continue;
                }

                path.add(nums[i]);
                used[i] = true;

                dfs(nums, len, depth + 1, path, used, result);

                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
    }
}
